import java.util.Map;
import java.util.Scanner;

/**
 * @Title: Dijkstra求最短路1
 * @Author 贾金博
 * @Package PACKAGE_NAME
 * @Date 2024/3/14 20:30
 * @description: 经典的图论
 */
public class Dijkstra求最短路1 {
    // 这里的n 是 500 m 是 1e5 n和m相差比较大
    public static Scanner sc = new Scanner(System.in);
    public static int n;
    public static int m;
    public static int[][] g = new int[510][510];
    public static int[] dis = new int[510]; // 到原点的距离
    public static boolean[] st = new boolean[510]; // 这个点 是不是已经定了

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        for(int i = 1; i <= n; ++ i ) {
            for(int j = 1; j <= n; ++ j ) {
                g[i][j] = i == j ? 0 : 0x3f3f3f;
            }
            dis[i] =0x3f3f3f;
        }

        dis[1] = 0; // 原点的距离是1

        for(int i = 1; i <= m; ++ i ) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            int value = sc.nextInt();
            g[x][y] = Math.min(g[x][y], value); // 这里是有向边
        }

        dijkstra();

        System.out.println(dis[n] == 0x3f3f3f ? -1 : dis[n]);
    }


    public static void dijkstra() {
        dis[1] = 0;
        //n个点 迭代n次 寻找
        for(int i = 1; i <= n; ++ i ) {
            int t = -1;
            for(int j = 1; j <= n; ++ j ) {
                if(!st[j] && (t == -1 || dis[j] < dis[t])) {
                    t = j; // 到原点里面最小的距离 前提是还没加入集合里面
                    //System.out.println("i = " + i + " t = " + t);
                }
            }
           // System.out.println("t = " + t);
            if(t > 0) {
                st[t] = true;
                //根据这个点 去更新其他的点
                for(int j = 1; j <= n; ++ j ) {
                    dis[j] = Math.min(dis[j], dis[t] + g[t][j]); // g[t][j]表明的是 t到j的最短距离
                }
            }
        }
    }
}
/**
 * 3 3
 * 1 2 2
 * 2 3 1
 * 1 3 4
 */